#include <iostream>
#include <vector>
#include <memory>

using namespace std;

#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
#define MAXNUM 9999 // 用于初始化哈希表的记录 key

typedef int Status;
typedef int KeyType;

// 哈希表中的记录类型
struct RcdType {
    KeyType key = MAXNUM; // 初始化为最大值
};

// 哈希表类型
struct HashTable {
    vector<RcdType> rcd;
    vector<int> tag;     // 对应的位，表示是否有元素
    int size = 0;
    int count = 0;
};

// 哈希表每次重建增长后的大小
vector<int> hashsize = {11, 31, 61, 127, 251, 503};
int index = 0;

// 初始哈希表
Status InitHashTable(HashTable &H, int size) {
    try {
        H.rcd.resize(size);
        H.tag.resize(size, 0); // 初始化 tag 为 0
        H.size = size;
        H.count = 0;
    } catch (...) {
        return OVERFLOW;
    }
    return OK;
}

// 哈希函数：除留余数法
int Hash(KeyType key, int m) {
    return (3 * key) % m;
}

// 处理哈希冲突：线性探测
void collision(int &p, int m) {
    p = (p + 1) % m;
}

// 在哈希表中查询
Status SearchHash(const HashTable &H, KeyType key, int &p, int &c) {
    p = Hash(key, H.size);
    int h = p;
    c = 0;
    while ((H.tag[p] == 1 && H.rcd[p].key != key) || H.tag[p] == -1) {
        collision(p, H.size);
        c++;
        if (c >= H.size) return UNSUCCESS; // 防止无限循环
    }

    if (H.tag[p] == 1 && key == H.rcd[p].key) return SUCCESS;
    return UNSUCCESS;
}

// 打印哈希表
void printHash(const HashTable &H) {
    cout << "key : ";
    for (const auto &rcd : H.rcd) {
        cout << rcd.key << " ";
    }
    cout << "\ntag : ";
    for (const auto &t : H.tag) {
        cout << t << " ";
    }
    cout << "\n\n";
}

// 插入哈希表
Status InsertHash(HashTable &H, KeyType key);

// 重建哈希表
Status recreateHash(HashTable &H) {
    auto orcd = H.rcd;
    auto otag = H.tag;
    int osize = H.size;

    InitHashTable(H, hashsize[index++]);
    // 把所有元素，按照新哈希函数放到新表中
    for (int i = 0; i < osize; i++) {
        if (otag[i] == 1) {
            InsertHash(H, orcd[i].key);
        }
    }
    return OK;
}

// 插入哈希表
Status InsertHash(HashTable &H, KeyType key) {
    int p, c;
    if (SearchHash(H, key, p, c) == UNSUCCESS) { // 没有相同 key
        if (c * 1.0 / H.size < 0.5) { // 冲突次数未达到上限
            H.rcd[p].key = key;
            H.tag[p] = 1;
            H.count++;
            return SUCCESS;
        } else {
            recreateHash(H); // 重构哈希表
            return InsertHash(H, key);
        }
    }
    return UNSUCCESS;
}

// 删除哈希表
Status DeleteHash(HashTable &H, KeyType key) {
    int p, c;
    if (SearchHash(H, key, p, c) == SUCCESS) {
        H.tag[p] = -1;
        H.count--;
        return SUCCESS;
    }
    return UNSUCCESS;
}

int main() {
    cout << "-----哈希表-----\n";
    HashTable H;
    vector<KeyType> array = {22, 41, 53, 46, 30, 13, 12, 67};

    // 初始化哈希表
    cout << "初始化哈希表\n";
    if (InitHashTable(H, hashsize[index++]) == SUCCESS) cout << "初始化成功\n";

    // 插入哈希表
    cout << "插入哈希表\n";
    for (auto key : array) {
        InsertHash(H, key);
        printHash(H);
    }

    // 删除哈希表
    cout << "删除哈希表中 key 为 12 的元素\n";
    if (DeleteHash(H, 12) == SUCCESS) {
        cout << "删除成功，此时哈希表为：\n";
        printHash(H);
    }

    // 查询哈希表
    cout << "查询哈希表中 key 为 67 的元素\n";
    int p, c;
    if (SearchHash(H, 67, p, c) == SUCCESS) cout << "查询成功\n";

    // 再次插入，测试哈希表的重建
    cout << "再次插入，测试哈希表的重建：\n";
    vector<KeyType> array1 = {27, 47, 57, 47, 37, 17, 93, 67};
    for (auto key : array1) {
        InsertHash(H, key);
        printHash(H);
    }

    return 0;
}
